//
// Created by fengg on 2020/3/27.
//

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

#define _CHAR(x)    *(char *)(x)
#define _INT(x)     *(int  *)(x)
#define _ADDR(x)     x->stack+x->item_size*x->top

#define on           1
#define off          0

/***********************************************************************************
 *                                  设置                                            *
 *                                                                                 *
 *      ENDING_CHAR             设定结尾字符                                         *
 *      sp                      后缀表达式中的分隔符,必须是字符串.                      *
 *      Verbose     on/off      沉余模式,就是输入一个式子会直接计算出结果,而不是后缀表达式  *
 *      RPN_Only    on/off      仅 输入后缀表达式,并输出其结果                          *
 *      Valid_Only  on/off      仅 校验输入式子的正确性(括号配对)                       *
 *                                                                                 *
 *      op_ack                                                                     *
 *          Operators acknowledged  操作符                                          *
 *                                                                                 *
 *      op_level                                                                   *
 *          Operators level         操作符优先级                                     *
 *                                                                                 *
 * *******************************************************************************/
/*-------------------------------------------------------------------------------*/
const char  NULL_CHAR        = '\0'                                                 ;
const char  ENDING_CHAR      = '\n'                                                 ;
const char  sp[]             = " "                                                  ;
const char  op_ack[]         = {'+','-','*','/','^','\0'}                           ;
const int   op_level[]       = { 0,  0,  1,  1,  2 }                                ;
int         Verbose          = on                                                   ;
int         RPN_Only         = off                                                  ;
int         Valid_Only       = off                                                  ;
/*--------------------------------------------------------------------------------*/
int op(int v1,int v2,char optor){
    int res = 0;
    switch (optor){
        case '+':
            res = v1+v2;
            break;
        case '-':
            res = v1-v2;
            break;
        case '*':
            res = v1*v2;
            break;
        case '/':
            res = v1/v2;
            break;

        default:
            break;
    }
    return res;
}
/*--------------------------------------------------------------------------------*/



/**
 * 为了实现多种数据类型的栈,这里使用void*
 * TO BE FIXED 命名不规范
 */
typedef struct {
    void *stack;
    int top;
    size_t item_size;
    int max_size;
} Stack ;

int init(Stack *s,size_t item_size,size_t num){
    s->top = -1;
    s->stack =  malloc(item_size*num);
    s->item_size = item_size;
    s->max_size = num;
    return 0;
}

int isEmpty(Stack *s){
    return s->top < 0;
}

int isFill(Stack *s){
    return s->top >= s->max_size-1;
}

int push(Stack *s,const void *v,size_t t){
    if(!isFill(s)){
        ++s->top;
        memcpy(_ADDR(s),v,t);
        return 1;
    }
    return 0;
}

void* pop(Stack *s){
    if(!isEmpty(s)){
        void *p = _ADDR(s);
        --s->top;
        return p;
    }

    return NULL;
}

void* peak(Stack *s){
    if(!isEmpty(s)){

        return _ADDR(s);
    }
    return NULL;
}



int is_valid(char *c){
    char open_p[] = {'(','{','[','\0'};
    char close_p[] = {')','}',']','\0'};
    int stack=0,i;
    for (i = 0; c[i]!= NULL_CHAR; ++i) {
        if(strchr(open_p,c[i]))
            ++stack;
        else if (strchr(close_p,c[i]))
            --stack;
    }
    return stack == 0;
}




/**
 * 判断两个操作符的优先级.
 *
 * @参数 op1 操作符
 * @参数 op2 操作符
 * @返回值 如果op1优先级高于op2返回大于零.如果低于,返回小于零.相等返回零
 */

int op_cmp(char op1, char op2) {
    int c1,c2;
    for (c1 = 0;op1 != op_ack[c1] && op_ack[c1] != NULL_CHAR; ++c1);
    for (c2 = 0;op2 != op_ack[c2] && op_ack[c2] != NULL_CHAR; ++c2);
    return op_level[c1] - op_level[c2];
}

int is_parentheses(char v){
    return v == '(' || v == ')';
}
/**
 * 从字符串x中获取一个Token
 * @参数 x 指向需要获取Token的字符串
 * @返回值  返回指向Token的指针
 */
char *get_token(const char *x){
    char *token = NULL;
    int i = 1;
    if(x[0] == ENDING_CHAR)
        return NULL;
    if(!isdigit(x[0]) && !isalpha(x[0])){
        if( !isdigit(x[-1])             &&
            !isalpha(x[-1])             &&
            !is_parentheses(x[-1])    &&
            !is_parentheses(x[0])){

            token = calloc(3,1);
            memcpy(token,"$",1);
            memcpy(&token[1],&x[0],1);

        } else{
            token = calloc(2,1);
            memcpy(token,&x[0],1);
        }

        return token;
    }
    for (;x[i] != NULL_CHAR && isdigit(x[i]) ; ++i);
    token = calloc(i+1,1);
    if(token != NULL){
        token = calloc(i+1,1);
        memcpy(token,x,i);
        return token;
    }
    return NULL;
}


/**
 * Manipulate RPN 维护后缀表达式.
 * 将Token插入后缀表达式中
 * @参数 s 指向`后缀表达式`
 * @参数 v 指向`Token`
 */
void man_rpn(char *s,char *v){

    if(s[0])
        strcat(s,sp);
    strcat(s,v);

}
/// OP_MODE
///     状态标识符,标记Tokens,用于后续Tokens的分发处理.
/// R_Parentheses_Mode
///     有括号状态标识符      # 待删除 , 需要更好的表示
/// L_Parentheses_Mode
///     左括号状态标识符      # 待删除 , 需要更好的表示
/// Number_Mode
///     数字状态标识符        # 待更名 , 需更切确的描述
/// Operator_Mode
///     操作符状态标示符
/// Single_Mode
///     目前唯一的作用就是标识单目运算符'-'
enum OP_MODE {
    R_Parentheses_Mode  =   -1,
    L_Parentheses_Mode  =   -2,
    Number_Mode         =    1,
    Operator_Mode       =    2,
    Single_Mode         =    5
};
/**
 * 获得s指向的Token所属模式
 * @参数 s 指向Token
 * @参数 mode 返回模式
 * @返回值 未定义
 */
int get_mode(char *s,int *mode){
    if(isdigit(s[0]) || isalpha(s[0]))
        *mode = Number_Mode;  // number_mode
    else if (s[0] == '(')
        *mode = L_Parentheses_Mode;
    else if (s[0] == ')')
        *mode = R_Parentheses_Mode;
    else if (!strcmp("$-",s))   //single op mode
        *mode = Single_Mode;

    else
        *mode = Operator_Mode; // op_mode
    return 0;
}
/**
 * 函数.待弃用.
 * @param token
 * @return
 */
size_t vail_len(char *token){
    size_t str_len = strlen(token);
    if(isdigit(token[0]) || isalpha(token[0]))
        return str_len;
    else {
//        for (; i < str_len; ++i) {
//            int j;
//            size_t op_ack_len = strlen(op_ack);
//            for (j = 0; j < op_ack_len; ++j) {
//
//            }
//        }
        return 1;
    }
}

int s2i(char *s){
    int temp =0;
    int i=0;
    while (s[i]!=NULL_CHAR && isdigit(s[i]))
        temp = temp*10+s[i++]-'0';
    return temp;
}
/**
 * 获得raw_str的后缀表达式,放入rpn_str中
 * @参数 raw_str 要获取的后缀表达式
 * @参数 rpn_str 后缀表达式
 * @返回值 int NOT USED
 */
int transfer(const char *raw_str,char *rpn_str){
    char *token;
    int mode;
    size_t raw_offset=0;
    Stack op_stack ={};

    init(&op_stack,3,50);

    /**
     *  逻辑
     *    String:   "1+5*9"
     *              上面的字符串在get_token函数作用下会被转换为一个个的Token
     *    Token:    "1","+","5","*","9"
     *              通过get_mode获得每个Token所属的状态/属性.
     *    OP_MODE:  Number_Mode,Operator_Mode,Number_Mode,...
     *              switch语句判断Token的状态/属性,做出对应的操作
     */
    while ((token = get_token(&raw_str[raw_offset])) != NULL){
        raw_offset += vail_len(token);
        get_mode(token,&mode);
        switch (mode){
            case Number_Mode:
                man_rpn(rpn_str,token);
                break;
            case Operator_Mode:
                while (!isEmpty(&op_stack)){
                    char op = _CHAR(peak(&op_stack));
                    if(is_parentheses(op) || op_cmp(token[0],op) > 0 )
                        break;
                    man_rpn(rpn_str,pop(&op_stack));
                }
                push(&op_stack,token,2);
                break;
            case Single_Mode:           //TODO 最好删掉,为了一个'-'不知道这样值不值
                man_rpn(rpn_str,"0");
                push(&op_stack,&token[1],2);
                break;
            case R_Parentheses_Mode:    // TODO 为了判定')',不知这样值不值
                while (!isEmpty(&op_stack) && _CHAR(peak(&op_stack)) != '('){
                    man_rpn(rpn_str,pop(&op_stack));
                }
                pop(&op_stack);
                break;
            case L_Parentheses_Mode:    // TODO 为了判定'(',不知这样值不值
                push(&op_stack,token,2);
                break;
            default:
                printf("Invalid Mode\nToken is %s\n",token);
        }
        free(token);
    }
    free(token);
    while (!isEmpty(&op_stack)){
        man_rpn(rpn_str,pop(&op_stack));
    }
    return 0;
}


size_t get_rpn_token(const char *rpn,char **token){
    size_t i=1;
    if(rpn[0] == NULL_CHAR || rpn[0] == '\n')
        return 0;
    while (rpn[i] != NULL_CHAR && rpn[i] != sp[0])
        ++i;
    *token = calloc(i+1,1);
    memcpy(*token,rpn,i);
    return i;
}



int eval(char *rpn_str){
    size_t rpn_offset = 0,token_len=0;
    Stack Number_stack = {};
    char *token;
    int number,mid_res=0;
    int mode;
    init(&Number_stack, sizeof(int),50);
    while ((token_len = get_rpn_token(&rpn_str[rpn_offset],&token))!= 0 ){
        rpn_offset += token_len+1;
        get_mode(token,&mode);
        switch (mode){
            case Number_Mode:

                number = s2i(token);
                push(&Number_stack,&number, sizeof(int));
                break;
            case Operator_Mode:
                mid_res=op(
                        _INT(pop(&Number_stack)),
                        _INT(pop(&Number_stack)),
                        token[0]

                        );
                push(&Number_stack,&mid_res, sizeof(int));
                break;
            default:
                printf("Invalid Mode\nThe Token Is %s",token);
        }

    }
    free(token);
    return _INT(pop(&Number_stack));
}

int main(){
    char *raw_str;
    char *rpn_str;
    size_t default_size = 0;
    int eval_res;

    raw_str = calloc(default_size,1);
    rpn_str = calloc(default_size,1);

    if(Valid_Only){
        getline(&raw_str,&default_size,stdin);
        printf("%d",is_valid(raw_str));
        return 0;
    }

    if(!RPN_Only){
        rpn_str = calloc(50,1);
        getline(&raw_str,&default_size,stdin);


        transfer(raw_str,rpn_str);
        if(Verbose)
            printf("RPN: ");
        printf("%s\n",rpn_str);
    } else {
        getdelim(&rpn_str,&default_size,'\n',stdin);


    }


    if(Verbose || RPN_Only){
        eval_res =  eval(rpn_str);
        printf("%d\n",eval_res);
    }

    return 0;
}
